1934B - Yet Another Coin Problem - CodeForces Solution

#include<bits/stdc++.h>

#ifdef jlocal
#include<jdebug/debug.hpp>
#else
#define debug(...) 0;
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
#define all(x) x.begin(),x.end()

const ld pi = 3.14159265358979323846L;
const ld sqrt2 = 1.41421356237309504880L;
const ll p = 73;
const ll mod = 1e9 + 123;

vi dp = {0, 1, 2, 1, 2, 3, 1, 2, 3, 2, 1, 2, 2, 2, 3, 1, 2, 3, 2, 3, 2, 2, 3, 3, 3, 2, 3, 3, 3, 4, 2};


int main(){
#ifndef jlocal
    ios::sync_with_stdio(0); cin.tie(0);
#endif
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        if (n <= 30){
            cout << dp[n] << endl;
            continue;
        }

        int base = n/15 - 1;
        int mod = dp[(n-base*15)%30];
        int res = base + mod;
        cout << res << endl;
    }
    return 0;
}